/*
 * @lc app=leetcode.cn id=980 lang=golang
 *
 * [980] 不同路径 III
 */

// 1. 深度优先
// @lc code=start
func uniquePathsIII(grid [][]int) (ans int) {
	start := make([]int, 2) // 开始节点
	end := make([]int, 2)   // 结束节点
	num := 0                // 可以通过的节点数量

	row := len(grid)       // 行数
	column := len(grid[0]) // 列数

	for i := 0; i < row; i++ {
		for j := 0; j < column; j++ {
			if grid[i][j] == 1 {
				start[0], start[1] = i, j
			}
			if grid[i][j] == 2 {
				end[0], end[1] = i, j
			}
			if grid[i][j] == 0 {
				num++
			}
		}
	}

	// 方向向量
	dr := []int{0, 0, 1, -1}
	dc := []int{1, -1, 0, 0}

	var dfs func(next []int, count int)
	dfs = func(next []int, count int) {
		if next[0] == end[0] && next[1] == end[1] && count == num+1 {
			ans++
			return
		}

		if count == 0 { // 是起点
			for i := 0; i < 4; i++ {
				dfs([]int{next[0] + dr[i], next[1] + dc[i]}, count+1)
			}
			return
		}

		// 在矩阵中 不是起点 不是终点 不是障碍物 不是已经走过的节点
		if next[0] < 0 || next[0] >= row || next[1] < 0 || next[1] >= column || grid[next[0]][next[1]] == -1 || grid[next[0]][next[1]] == 2 || grid[next[0]][next[1]] == 1 || grid[next[0]][next[1]] == 3 {
			return
		}

		// 能走到这里的矩阵类型必定是0
		grid[next[0]][next[1]] = 3 // 代表已经走过了这个节点

		for i := 0; i < 4; i++ {
			dfs([]int{next[0] + dr[i], next[1] + dc[i]}, count+1)
		}

		grid[next[0]][next[1]] = 0 // 复原

	}

	dfs(start, 0)
	return
}

// @lc code=end

